The present invention relates to the field of computer arithmetic and more particularly to the field of binary addition.
Two of the most critical factors in determining the performance of a computer system are the internal clock frequency and the datapath width of the processor. A far more powerful computer system can be built with a 200 MHz, 32 bit processor than with a 8 MHz, 8 bit processor. However, there is an inherent conflict between these two factors in a key component of a processor, a binary adder. The conflict results from the dependence of the latency on the width of a typical binary adder. For example, the latency of a parallel ripple adder depends on the operand width because sufficient time must be allowed for a carry bit to propagate through one adder stage for every bit of the operand width. The latency can be reduced by using a carry lookahead technique wherein the carry bits into every stage can be calculated simultaneously by expressing every carry bit as a function of all of the preceding, simultaneously available operand bits. However, the carry lookahead technique is limited by the fan-in restrictions of the circuit technology, in that additional levels of logic are needed as the number of inputs to the highest order stage increases. These additional levels increase the latency, so again, the latency depends on the operand width. In response to this dependence of adder latency on adder width, a novel approach to binary addition has been developed.
An adder for calculating an N bit sum from an N bit augend and an N bit addend is disclosed. The adder comprises a first circuit for speculatively calculating bit Nxe2x88x921 of the sum based only on bit Nxe2x88x921 of the augend, bit Nxe2x88x921 of the addend, and a limited carry bit. The adder also comprises a second circuit for calculating the limited carry bit based only on K bits of the augend and K bits of the addend, where K is less than Nxe2x88x921. The adder also comprises a third circuit for detecting a potential difference between the limited carry bit and an unlimited carry bit.